By yusijia

Updated:

Contents
  1. 1. 题目大意：

题目大意：

　　有编号分别为1~N的N本书，准备分给N个人，每个人阅读兴趣用一个二维数组表示。

  • 1：喜欢这本书；
  • 0：不喜欢这本书。
  • Like[i][j] = 1，i喜欢书j；
  • Like[i][j] = 0，i不喜欢书j。
  • 问：如何分书才能使得所有人都满意，输出第i个人分得的书的编号，如果有多个答案
    输出序列数小的那一组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79


#include <cstdio>
#include <cstring>
#define MAXN 555

int mp[MAXN][MAXN];
int ans[MAXN];
bool vis[MAXN];
int n;

bool Search(int m)                      //输出序列数最小的一组答案
{
    if(m == n)  return true;
    for(int i = 0; i < n; i++)if(!vis[i] && mp[m][i]){//判断第i本书是否选过，且m是否喜欢第i本书
        ans[m] = i + 1;                 //第i本书被选了，这里的存的i是以1为基数的i
        vis[i] = 1;
        if(Search(m + 1))               //剩下的能否人手一本，如果不能的话就不选第i本书，继续找下一本书
            return true;
        vis[i] = 0;
    }
    return false;
}

bool searchs(int m)                     //输出所有可能的情况
{
    if(m == n){
        printf("%d", ans[0]);
        for(int i = 1; i < n; i++)
            printf(" %d", ans[i]);
        printf("\n");
    }
    for(int i = 0; i < n; i++)if(!vis[i] && mp[m][i]){
        ans[m] = i + 1;
        vis[i] = 1;
        searchs(m + 1);
        vis[i] = 0;
    }
    return false;
}
int main()
{
    freopen("input.txt", "r", stdin);
    while(scanf("%d", &n) != EOF){
        memset(ans, 0, sizeof(ans));
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                scanf("%d", &mp[i][j]);
            }
        }
        if(Search(0)){
            printf("%d", ans[0]);
            for(int i = 1; i < n; i++)
                printf(" %d", ans[i]);
            printf("\n");
        }
        printf("\n");
        memset(ans, 0, sizeof(ans));
        memset(vis, 0, sizeof(vis));
        searchs(0);
    }
    return 0;
}

/*
5
0 0 1 1 0
1 1 0 0 1
0 1 1 0 1
0 0 0 1 0
0 1 0 0 1

3 1 2 4 5

3 1 2 4 5
3 1 5 4 2

*/
Contents
  1. 1. 题目大意：